
def binarySearch(array, val, isLeft=True, isStrong=True, first=None, last=None, key=None):
    if not array:
        raise ValueError()

    if key is None:
        key = lambda x: x

    lo = first or 0
    hi = last  or len(array) - 1

    while hi - lo > 1:
        mid     = (hi + lo) / 2
        curVal  = key(array[mid])

        if curVal > val:
            hi = mid
        elif curVal < val:
            lo = mid
        elif isLeft:
            hi = mid
        else:
            lo = mid

    if isLeft:
        if isStrong:
            if key(array[lo]) == val:
                return lo
            if key(array[hi]) == val:
                return hi
        else:
            if key(array[lo]) >= val:
                return lo
            if key(array[hi]) >= val:
                return hi
    else:
        if isStrong:
            if key(array[hi]) == val:
                return hi
            if key(array[lo]) == val:
                return lo
        else:
            if key(array[hi]) <= val:
                return hi
            if key(array[lo]) <= val:
                return lo

    raise ValueError()

def binarySearchRange(array, fromValue, toValue=None, key=None):
    if toValue is None:
        toValue = fromValue
        isStrong = True
    else:
        isStrong = False

    first = binarySearch(array, fromValue, isLeft=True,  isStrong=isStrong, key=key)
    last  = binarySearch(array, toValue,   isLeft=False, isStrong=isStrong, key=key, first=first)

    return first, last

def matchBySimpleWildcard(name, wildcard, fromBeginning=False):
    keys = wildcard

    index  = 0
    offset = 0

    if fromBeginning:
        if not name.startswith(keys[0]):
            return False

        index  = 1
        offset = len(keys[0])

    ok = True
    while index < len(keys):
        key = keys[index]
        offset = name.find(key, offset)
        if offset == -1:
            return False

        offset = offset + len(key)
        index += 1

    return True
